The quality of images reproduced over a television, a display panel, or by a printing system may be judged with respect to three characteristics: tone scale, image sharpness, and graininess. For digital type of image reproduction devices such as display panels, television monitors, and dot matrix printers there is a direct dependence of these characteristics on the reproduction device system parameters. The tone scale image quality depends on both the system tone reproduction curve which defines a gray scale transformation from the original to the reproduced image, and on the number of levels of gray the system is capable of reproducing. The sharpness factor is directly affected by the x and y resolutions of the reproduction device. Higher resolution devices are generally better at reproducing fine details, thereby yielding sharper images. Finally, graininess refers to those image noises which are usually process related and are not part of the original image.
There are three classes of images each of which has its own characteristics affecting the process of image reproduction. Line copy imagery is composed of typographic letters and symbols, lines, and solid filled areas of a single gray level. A continuous tone imagery is one which has an apparent continuum of gray levels as in photographs and natural scenes. Halftone imagery is an approximation by the printing press to reproduce the continuum of gray scale by varying the printed dot sizes prearranged in a geometric pattern. Variations in printed dot size yield a varying percent of light reflection from the printed image thereby creating the apparent gray scale illusion. Since line copy imagery is binary, consisting of only two levels of gray which is either black or white, its reproduction does not involve tone scale considerations. It does require the capability of reproducing fine details and smooth edges which is characteristic of the typographic fonts. Continuous tone imagery reproduction requires both fine detail as well as tone scale capabilities. Halftone imagery is basically binary, therefore its reproduction should be like that of the line copy imagery. However, its reproduction is complicated by the presence of a strong spatial frequency not contained in the original which may result in unwanted Moire patterns or other artifacts in the reproduced images.
Television has excellent tone scale reproducibility because it is capable of displaying many levels of gray. Coupled with adequate x and y resolutions, television is an excellent continuous tone reproduction device. On the other hand, modern displays and dot matrix printers are basically binary devices which display or print fixed size dots having no gray scale capability. With sufficient x and y resolution, these devices are good for reproducing line copy imagery and possibly halftone pictorials. The best method for achieving gray scale representation by the binary devices is through pseudo-halftone techniques which mimic the halftone process. However, this is done at the expense of the x and y resolution. As practiced in the graphic arts industry, halftone dots are created from 8 by 8 to 16 by 16 square matrix blocks of binary pixels, which give from 65 to 257 levels of gray. To attain the 100 to 120 lines per inch screen size printing, the original binary device must have resolutions of 800 to almost 2000 dots per inch. Modern dot matrix printers of the non-impact type have resolutions in the range from 200 to 480 dots per inch. They can produce near typographic quality letters and very good line copy imagery. However, pseudo-halftone techniques for gray scale reproduction drastically reduce their resolution to unacceptable levels. Any further increase in the resolution of these display and printing devices must be accompanied by drastic increases in the electronic memory and other component requirements, which make the cost prohibitive.
The role of image processing is to decide whether or not to display or print a fixed size dot at each pixel location such that the reconstructed image closely resembles the original. Stoffel and Moreland in their article "A Survey of Electronic Techniques for Pictorial Reproduction", IEEE Transactions on Communications, Vol. COM-29, No. 12, 1981, and Jarvis, Judice and Hinke in their article "A Survey of Techniques for the Display of Continuous Tone Pictures on Bilevel Displays", Computer Graphics and Image Processing, Vol. 5, 1976 discuss in detail the subject. For line copy imagery reproduction, simple thresholding can yield excellent results. For continuous tone imagery, the recreation of gray scale tone levels are either by means of halftone methods or dispersed halftone methods. For the reproduction of halftone originals, the reproduction algorithm must avoid introducing its own spatial frequency which may interfere with the strong spatial frequency associated with the halftone screen and cause Moire patterns.
In pseudo-halftone methods of gray scale generation, each halftone cell is composed of a number of individual print or display pixels clustered together. The most common form of the halftone cells is a N by N square pixel matrix of binary fixed sized dots. The general concept of the pseudo-halftone methods is to print or display a computed number of dots within a halftone cell achieving a gray scale value average approximating the averaged density value of the original. David Behane, Lewis Spradley, Lysle Cahill, and William Marshall in U.S. Pat. No. 3,604,846 disclosed a halftone method where the order of printing or displaying the dots is prescribed within the halftone cell by successively placing dots within the halftone cell connected together to imitate the formation of a single halftone dot. In contrast, James Berry, Anthony Hauser, Kurt Knuth, and Gary Ollendick in U.S. Pat. No. 3,977,007 disclosed a method of "dispersed" halftone process where the order of placing the dot is also predetermined but in such a way that successively placed dots are displaced from each other. Paul Roetling in U.S. Pat. No. 4,051,536 and R. W. Pryor, G. M. Cinque, and A. Rubinstein in their article "Bilevel Image Displays--A New Approach", Proceeding of the S.I.D., Vol 19/3, 1978 both disclosed dispersed type of halftone methods where the choice of the dot placement location is made based on the local density information of the original within that halftone cell. While the pseudo-halftone methods very ably reproduce gray scale values for a halftone cell in the averaged sense, it suffers from a loss of resolution. Hence, small image details within each halftone cell are generally not well represented.
A second method is "Error Diffusion" where the decision to print or not to print a pixel is made based on the local scanned density information from the original as well as on the gray scale density errors committed by its already processed neighbors. Robert Floyd and Louis Steinberg in their article "An Adaptive Algorithm for Spatial Gray Scale", Proceedings of the Society for Information Display, Vol. 17/2 1976 and Stephen Temple in U.S. Pat. No. 4,339,774 both disclosed different implementations of the method. This method is capable of gray scale reproduction while providing local detail recreation. However, unless the error neighborhood taken into consideration for the computations is sufficiently large, the reproduced image tends to have a wormy appearance in smooth density areas. W. Thomas Warren in U.S. Pat. No. 4,196,454 disclosed a method of processing halftone image data which also diffuses the density error to the next halftone cell.
The pseudo-halftone methods generally can not be used to reproduce image originals which itself is halftone because of the strong tendency of producing Moire patterns in the recreation. Keith T. Knox in U.S. Pat. No. 4,246,614 disclosed a method of halftone processing with a built in shift control to align the reproduction halftone screen with that of the original image to avoid Moire patterning. On the other hand, error diffusion methods are generally suitable for halftone reproduction because they do not have a built in screen frequency in their processes.
All of the above mentioned digital image processing algorithms are for binary fixed size print dots or display spots. They all are able to reproduce well some of the image types: text and line drawing, continuous tone images, and halftone pictorials. The present generation of printers and displays poorly mimic the halftone technique of the printing industry because of insufficient dot resolution. It would be advantageous if the printers and displays could produce halftones as a natural part of their process.
Thus there is a need for an image processing algorithm which can generate gray scale in images without sacrificing image resolution. Also, there is the need for a single algorithm which is universally applicable to all types of imagery reproduction.